Memory referencing in a computer system typically follows one of two paradigms: a physical address model or a virtual address model. The physical model is most direct and therefore fast. A limitation of the physical model is the requirement that programs be written to run within the bounds of the particular computer systems physical memory space and at specific locations within that physical memory space. The virtual model is much more flexible, but the time required to translate from virtual space to physical space at run time can contribute detrimentally to the general performance of the computer system.
The definition of physical memory is the implementation, in physical devices, of a storage medium such that storage locations are physically contiguous from "0", or the lowest address, to some upper bound that is limited by the nature of the storage medium. The storage medium may allow random access to the individual storage locations or sequentially to the individual storage locations depending upon the nature of the physical storage medium. A computer system memory storage medium is typically implemented as Dynamic Random Access Memory integrated circuits. The granularity of memory is also important to this situation. Granularity refers to the smallest physical number of memory bits that can be addressed by the computer system hardware. This is defined as a memory word and the width in bits is dictated by the physical architecture of the computer system. A memory word may consist of one or more bytes (eight bit groups) of data.
There are two general models of mapping program data and program code structures onto a physical memory space. These are the segmentation model and the paged model. An important definition is that of a "block". A block of memory is the amount of physical memory large enough to contain a segment, in the segmented model, or one page, in the paged model.
The segmentation model is the most space efficient since it reserves exactly the amount of physical space, in words, required to exactly store the program data or code structures. A big disadvantage to the segmentation model is the requirement to map the entire virtual segment into a block of contiguous physical space. Large program code and data structures tend to limit the number of different programs that can co-exist in physical memory due to virtual segment size requirements, and therefore limit the multi-processing capability of the computer system.
The paged model requires that physical memory be broken down into chunks of uniformly sized block of memory, called pages, each block containing the same amount of contiguous physical memory. The page size (block size) is usually fixed by the physical architecture of the computer system and is typically in power of 2 sized (i.e. a page may be a block of 256, 512, 1024, etc. words of contiguous physical memory). An advantage of the paged model is that it eliminates the requirement of maintaining an entire program data or code structure in physical memory; the individual pages that make up the program data or code structure may be located in any order anywhere in physical memory. The paged model allows for efficient multi-programming by allowing some of the pages of a program's code or data structure to be swapped out of physical memory and be replaced by pages from some other unrelated program. The paged memory model allows implementation of efficient virtual to physical address translation mechanisms if page size is a power of 2. A major disadvantage of the paged model is the waste of physical memory space that occurs when program code and data structures are smaller than the space required for a page.
The ideal implementation of a physical model would allow some combination of the segmented and paged models. This invention defines the embodiment of an efficient mechanism that implements a combined paged-segmented model. This invention allows the efficiency of smaller non-swappable blocks and the resulting performance improvements to multiprocessing, along with the conservation of memory space allowed by the segmented model.
The logical implementation of a virtual memory system that would be a user of the paged-segmented physical model will typically use a logical structure called a "Pointer" to provide the virtual address in the virtual address model. The pointer is an abstract device that allows a program to reside in virtual rather than physical memory space and therefore detached from the physical implementation. This allows for efficient multi-processing since the only effect that physical memory size has on the computing environment is one of performance.
Translations of virtual addresses to physical addresses in a paged memory system are typically implemented in special mechanisms known in the art as Translation Lookaside Buffers (TLB). These can be implemented in special hardware structures to improve efficiency, but sometimes are implemented as "soft" code routines. The mechanism in this embodiment consists of a unique implementation of a content addressable memory (CAM) architecture for efficient translation of paged segments and un-paged segments in hardware. This implementation is essential to the hardware pointer update mechanism enabling a rapidly updated pointer.